package class08

import (
	"math"
	"sort"
)

/*
	题目五：
		先给出可整合数组的定义：如果一个数组在排序之后，每相邻两个数
		的绝对值都为1，则该数组为可整合数组。例如：[5,3,4,6,2]
		排序之后为[2,3,4,5,6],符合每相邻两个数的绝对值都为1，所以
		这个数组为可整合数组。给定一个整形数组 arr, 请返回其中最大
		可整合子数组的长度。例如：[5,5,3,2,6,4,3]，的最大可整合子数组
		为[5,3,2,6,4]，所以返回 5

	思路：
		1. 先从数据状况入手
		2. 考虑 可整合数组 的定义是否可以转化
		3. 可整合优化
			3.1 无重复值
			3.2 max-min = 个数 - 1
			此时与 可整合的效果是一样的

	方式一：O(N^3*logN)
		1）列出所有的开头与结尾的位置
		2）拷贝一份数据，排序，判断是否可整合

	方式二：O(N^2)
		1. 使用优化后的定义，对流程进行优化
		2. 初始化一个set记录重复值
		3. 使用一个map记录 l-r 之间的数的集合，如果遍历r的时候有重复直接退出
		4. 如果个数-1满足 max-min 则收集答案
*/
func getLIL1(arr []int) int {
	if len(arr) < 1 {
		return 0
	}
	var ans int
	for i:=0; i<len(arr); i++ {
		for j:=i; j<len(arr); j++ {
			if isCanMergeArr(arr, i, j) {
				ans = max(ans, j-i+1)
			}
		}
	}
	return ans
}

func isCanMergeArr(arr []int, l, r int) bool {
	newArr := make([]int, r-l+1)
	copy(newArr, arr[l:r+1])
	sort.Ints(newArr)
	for i:=1; i<len(newArr); i++ {
		if newArr[i] != newArr[i-1] + 1 {
			return false
		}
	}
	return true
}

func getLIL2(arr []int) int {
	if len(arr) < 1 {return 0}
	numSet := map[int]bool{}
	var maxN, minN, ans int
	for l:=0; l<len(arr); l++ {
		numSet = map[int]bool{}
		maxN = math.MinInt
		minN = math.MaxInt
		for r:=l; r<len(arr); r++ {
			if numSet[r] {
				break
			}
			maxN = max(maxN, arr[r])
			minN = min(minN, arr[r])
			numSet[r] = true
			if maxN - minN == r - l {
				ans = max(ans,  r-l+1)
			}
		}
	}
	return ans
}